package digui;

/**
 * @Description 递归（斐波那契）
 * 第一步：找到出口
 * 第二步：找到数据间的关系
 * @Author zzj
 * @Date 2020/7/19 23:30
 */
public class DiGuiDemo01 {
    public static void main(String[] args) {
        // 求斐波那契数列：1,1,2,3,5,8,13,21......

        // 1. 求第二十个数
        int[] arr = new int[20];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < arr.length; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        System.out.println(arr[19]);


        // 2. 递归求法

        System.out.println(diGui(20));
    }

    // 递归求法：
    static int diGui(int index) {
        // 递归出口（第一个月和第二个月为1）
        if (index == 1 || index == 2)
            return 1;
        return diGui(index - 1) + diGui(index - 2);
    }
}
